package com.lft.josephu;

public class JosephuUtil {
	
	/**
	 * 【创建环形链表】
	 * @param nums 节点个数
	 * @return 返回创建好的环形链表
	 */
	public static Boy create(int nums) {
		// 对数量进行进行验证
		if (nums < 1) {
			System.out.printf("nums的值 %d 不正确，必须大于1", nums);
			return null;
		}
		// 环形链表头
		Boy first = null;
		// 辅助指针，帮助构建环形链表
		Boy curBoy = null;
		for (int i = 1; i <= nums; i++) {
			Boy boy = new Boy(i);
			// 如果是第一个节点。
			if (i == 1) {
				first = boy;
				// 构成环
				first.setNext(first);
				// 让 curBoy 指向第一个。
				curBoy = first;
			} else {
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
		return first;
	}
	
	/**
	 * 【添加节点】
	 * @param first  原始环形链表
	 * @param newBoy 新节点
	 * @return 返回添加之后的环形链表
	 */
	public static Boy add(Boy first, Boy newBoy) {
		if (first == null && newBoy == null) {
			return null;
		}
		if (first == null) {
			return newBoy;
		}
		if (newBoy == null) {
			return first;
		}
		// 定义一个临时指针。
		Boy curBoy = first;
		// 遍历链表。当指针的下一个会指到first节点。就遍历完成。
		while (curBoy.getNext() != first) {
			curBoy = curBoy.getNext();
		}
		// 添加新节点。
		curBoy.setNext(newBoy);
		newBoy.setNext(first);
		
		// 将添加好的环形链表返回。
		return first;
	}
	
	/**
	 * 【按序号添加】
	 * @param first  原始约瑟夫环
	 * @param newBoy 新节点
	 * @return 返回添加之后的约瑟夫环
	 */
	public static Boy addByOrder(Boy first, Boy newBoy) {
		if (first == null && newBoy == null) {
			return null;
		}
		if (first == null) {
			return newBoy;
		}
		if (newBoy == null) {
			return first;
		}
		// 标志，用于标记是否有重复。
		boolean flag = false;
		Boy curBoy = first;
		while (curBoy.getNext() != first) {
			// 说明找到了。插在当前节点之前。
			if (curBoy.getNo() > newBoy.getNo()) {
				break;
			}
			// 说明有重复。
			if (curBoy.getNo() == newBoy.getNo()) {
				flag = true;
				break;
			} else {
				// 否则指针后移一位。
				curBoy = curBoy.getNext();
			}
		}
		// 判断是否有重复。
		if (flag) {
			System.out.printf("添加的节点的编号 %d 已经存在，无法添加。\n", newBoy.getNo());
			return first;
		} else if (curBoy == first) {
			// 添加的节点的位置，正好在第一个节点之前。
			// 将新节点的下一个设置为first
			newBoy.setNext(first);
			// 创建一个临时指针。
			Boy temp = first;
			// 遍历原约瑟夫环,找到原来环中的最后一个。
			while (temp.getNext() != first) {
				temp = temp.getNext();
			}
			// 将原来最后一个的下一个设置为新节点。
			temp.setNext(newBoy);
			// 然后将新节点，设置为头节点。
			first = newBoy;
		} else {
			// 如果正好是最后一个节点。上面的循环不会比较编号。
			if (curBoy.getNo() == newBoy.getNo()) {
				// 如果重复，提示语。
				System.out.printf("添加的节点的编号 %d 已经存在，无法添加。\n", newBoy.getNo());
				// 返回原约瑟夫环。
				return first;
			} else if (curBoy.getNo() > newBoy.getNo()) {
				// 如果正好是最后一个节点。上面的循环不会比较编号。
				// 如果不重复。定义临时指针。
				Boy temp = first;
				// 遍历找到curBoy的前一个。
				while (temp.getNext() != curBoy) {
					temp = temp.getNext();
				}
				// 将新节点的下一个设置为curBoy
				newBoy.setNext(curBoy);
				// 将前一个节点的下一个设置为新节点。
				temp.setNext(newBoy);
			} else {
				newBoy.setNext(curBoy.getNext());
				curBoy.setNext(newBoy);
			}
			
		}
		// 将添加好的约瑟夫环返回。
		return first;
	}
	
	/**
	 * 【删除节点】
	 * @param first 原始链表
	 * @param boy   要删除的链表节点
	 * @return 返回删除之后的链表
	 */
	public static Boy delete(Boy first, Boy boy) {
		if (first == null) {
			System.out.println("约瑟夫环为空。");
			return null;
		}
		// 判断是否只有一个节点。
		if (first.getNext() == null) {
			// 当只有一个节点的时候，只要要删除的节点的编号跟当前节点的编号一致就可以直接返回一个空
			if (first.getNo() == boy.getNo()) {
				return null;
			} else {
				// 否则就输出原链表。提示，要删除的节点不存在。
				System.out.printf("要删除的节点编号 %d 不存在，无法删除。\n", boy.getNo());
				return first;
			}
		}
		// 当链表不只一个节点的时候。
		// 创建临时指针。
		Boy curBoy = first;
		// 创建临时指针，指向前面一个。
		Boy temp = first;
		while (temp.getNext() != first) {
			temp = temp.getNext();
		}
		// 标记，标记出找到的要删除的节点。
		boolean flag = false;
		while (true) {
			if (curBoy.getNo() == boy.getNo()) {
				flag = true;
				break;
			} else if (curBoy.getNext() == first) {
				// 如果下一个节点就是 first 那么遍历完成了。
				break;
			} else {
				// 否则 两个指针都往后移一位。
				curBoy = curBoy.getNext();
				temp = temp.getNext();
			}
		}
		if (flag) {
			// 判断一下，当前节点是不是头节点。
			if (curBoy == first) {
				// 如果是头节点。将curBoy的下一个节点。赋值给first
				first = curBoy.getNext();
				// 将temp的下一个节点，设置为first
				temp.setNext(first);
			} else {
				// 只要不是头节点。将temp的下一个节点指向curBoy的下一个节点
				temp.setNext(curBoy.getNext());
			}
		} else {
			// 其他情况就是没有找到。
			System.out.printf("要删除的节点编号 %d 不存在，无法删除。\n", boy.getNo());
			return first;
		}
		return first;
	}
	
	/**
	 * 【约瑟夫环出环顺序】
	 * @param first    原始链表。
	 * @param startNo  开始位置。
	 * @param countNum 每次数的数
	 */
	public static void countBoys(Boy first, int startNo, int countNum) {
		// 计算出节点数量
		int count = getCount(first);
		// 判断约瑟夫环链表是否为空
		if (first == null || startNo < 1 || startNo > count) {
			System.out.println("链表为空，或参数输入有误");
			return;
		}
		// 判断是否只有一个节点
		if (first.getNext() == null) {
			System.out.println(first);
		}
		
		// temp 记录开始位置的前一个位置。
		Boy temp = first;
		while (temp.getNext() != first) {
			temp = temp.getNext();
		}
		
		// 定位到开始位置。
		for (int i = 1; i < startNo; i++) {
			first = first.getNext();
			temp = temp.getNext();
		}
		
		for (int i = count; i > 0; i--) {
			// 开始数数
			for (int j = 0; j < countNum - 1; j++) {
				temp = temp.getNext();
				first = first.getNext();
			}
			// 输出这个节点。
			System.out.println(first);
			
			// 删除这个节点
			if (first.getNext() == first) {
				// 表示遍历结束了。
				return;
			} else {
				// 将first也后移一位。
				first = first.getNext();
				// 将temp的下一节点设置为first的下一个节点。
				temp.setNext(first);
			}
		}
	}
	
	/**
	 * 【计算节点数量】
	 * @param first 原始链表
	 * @return 节点数量
	 */
	public static int getCount(Boy first) {
		// 记录一下总共的节点数量
		int count = 0;
		Boy temp = first;
		while (true) {
			count++;
			if (temp.getNext() == first) {
				break;
			} else {
				temp = temp.getNext();
			}
		}
		return count;
	}
	
	/**
	 * 遍历约瑟夫环
	 * @param first 需要遍历的约瑟夫环
	 */
	public static void list(Boy first) {
		if (first == null) {
			System.out.println("约瑟夫环为空。");
			return;
		}
		// 定义一个临时指针。
		Boy curBoy = first;
		
		while (true) {
			// 打印当前节点
			System.out.printf("小孩的编号 %d \n", curBoy.getNo());
			// 如果当前节点的下一个节点就是 first 说明遍历完成。
			if (curBoy.getNext() == first) {
				break;
			}
			// 否则后移 curBoy
			curBoy = curBoy.getNext();
		}
	}
}